HashMap

2024-01-15 00:18| 来源: 网络整理| 查看: 265

HashMap 中如何确定元素的位置

众所周知，在 jdk 1.7 中，HashMap 底层是由数组 + 链表的方式实现的，那我们在使用 HashMap 的时候，是如何将我们的 key-value put 到 HashMap 中的呢

HashMap 存放原理

在理解 HashMap 的存放原理前，我们先来回想一下数组，当我们想给数组中的一个元素进行赋值时，我们至少需要知道两个条件，一是数组的引用名称，二是想要被赋值的数组元素的索引，即array[i]中的array和i

我们再来看看，在 jdk 1.7 中 HashMap 的结构：在这里插入图片描述从上图我们可以看到，HashMap 的主体是一个数组，这个数组中存储的元素是一个Entry类型的变量，这个变量有四个属性：Object key、Object value、int hash、Entry next，当两个元素经过计算后的数组下标相同时，就是所谓的发生了 Hash 碰撞，这时，就需要在数组发生 Hash 碰撞的位置构造一个链表，将发生碰撞的元素以链表的形式，存放在数组中

了解了 HashMap 的构成，我们知道 HashMap 的本质也是数组，既然我们想向数组里 put 元素，那我们必然需要知道数组的引用名称和要被 put 的位置的下标，可是 HashMap 的 put 方法只有 key 和 value 两个参数，没有 int 类型的 index，那 HashMap 是如何确定每个元素会被存放到数组的哪个位置呢？

这里我们看一下 HashMap 源码中的 put 部分：

public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } addEntry(hash, key, value, i); return null; }

这里我们暂且不讨论其他部分，直接看第 8 行代码，结合下面的table[i]等变量可以看到，这行代码通过indexFor函数返回的值，正是经过计算的数组下标，也就是说，HashMap 会在 put 元素时，通过元素的 hash 值以及当前数组的长度，来确定一个下标来存放元素

这时我们不妨想一想，hash 值一般都是一个十分巨大的整数，例如12345643、327864322等等（都是我瞎打的），而数组的长度一定是一个十分有限的数，假设是8，我们正常想通过这两个数来获取一个0~7的正数下标要怎么做？毫无以为，用hash % table.length，这样不管 hash 是一个多大的数，我们都可以得到一个在数组索引范围内的整数，那 HashMap 的 indexFor 函数中是如何做的呢？

HashMap 的 indexFor 函数

这里我们直接看 indexFor 函数的代码：

/** * Returns index for hash code h. */ static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }

代码很短，只有一行，我们可以看到，HashMap 中是通过 hash 和数组长度减一得到的结果进行一次&运算，这里我们要先清楚&运算的概念：将两个二进制数进行按位&操作时，只有两个数对应的位上都为 1，结果为 1，否则都为 0

我们不妨带进来一个数算一遍，这样结果比较直接，假设我们的 h 的二进制表示是1101 0110（我瞎编的），数组的长度是8，二进制就是0000 1000，这时我们先进行length - 1的操作，得到0000 0111，这时再与 hash 进行&操作时，可以得到0000 0110，即十进制的6，而 HashMap 的容量，即数组的长度永远都是2的次方，也就是说，table.length的二进制表示永远都是一个1，其余都是0的状态，例如2的4次方16是0001 0000，5次方32是0010 0000，那也就是说明，table.length - 1得到的值永远都是前一半都是0，后一半都是1，这种结构再与 hash 进行&操作时，得到的结果就和hash % table.length一样了！

【本文地址】

公司简介

联系我们